package com.lw.leetcode.hash.b;

import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * 2001. 可互换矩形的组数
 *
 * @author liw
 * @version 1.0
 * @date 2022/3/5 15:02
 */
public class InterchangeableRectangles {

    public long interchangeableRectangles(int[][] rectangles) {
        Map<Long, Long> map = new HashMap<>();
        long res = 0;
        for (int[] arr : rectangles) {
            int gcd = find(arr[0], arr[1]);
            long temp = (((long) arr[0] / gcd) << 32) + arr[1] / gcd;
            long c = map.getOrDefault(temp, 0L);
            res += c;
            map.put(temp, c + 1);
        }
        return res;
    }

    private int find(int a, int b) {
        return b == 0 ? a : find(b, a % b);
    }

}
